package demo_0717;

public class T6_0408 {
    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }
    }

    TreeNode head;
    TreeNode prev;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;

        Convert(pRootOfTree.left);

        if (prev == null) {
            head = pRootOfTree;
            prev = pRootOfTree;
        } else {
            prev.right = pRootOfTree;
            pRootOfTree.left = prev;
            prev = pRootOfTree;
        }

        Convert(pRootOfTree.right);
        return head;
    }


    /*
    解题思路：
      1. 特殊情况处理--空树
      2. 中序遍历二叉搜索树，将遇到的每个节点保存到ArrayList中，此时ArrayList中的节点就是有序的
      3. 处理ArrayList除第一个和最后一个外的每个节点，让其left指向前一个，right指向后一个
      4. 单独处理第一个的left和最后一个节点的right

     import java.util.ArrayList;
    public class Solution {
        // 中序遍历二叉搜索树，将遇到的节点保存到ArrayList中
        // 此时：ArrayList中的节点已经有序了
        void inorder(TreeNode root, ArrayList<TreeNode> list){
            if(null != root){
                inorder(root.left, list);
                list.add(root);
                inorder(root.right, list);
            }
        }

        public TreeNode Convert(TreeNode pRootOfTree) {
            if(null == pRootOfTree){
                return null;
            }

            // 中序遍历之后，节点已经有的保存到list中了
            ArrayList<TreeNode> list = new ArrayList<>();
            inorder(pRootOfTree, list);

            // 除第一个和最后一个节点外，其余每个节点：left指向前一个，right指向后一个
            int size = list.size();
            for(int i = 1; i < size-1; ++i){
                TreeNode cur = list.get(i);
                cur.left = list.get(i-1);
                cur.right = list.get(i+1);
            }

            // 处理第一个节点的right 和 最后一个节点的left
            if(size > 1){
                list.get(0).right = list.get(1);
                list.get(size-1).left = list.get(size-2);
            }

            return list.get(0);
        }
    }*/
}
